/*
 *  This file is part of the Jikes RVM project (http://jikesrvm.org).
 *
 *  This file is licensed to You under the Eclipse Public License (EPL);
 *  You may not use this file except in compliance with the License. You
 *  may obtain a copy of the License at
 *
 *      http://www.opensource.org/licenses/eclipse-1.0.php
 *
 *  See the COPYRIGHT.txt file distributed with this work for information
 *  regarding copyright ownership.
 */
package org.mmtk.utility.heap;

import org.mmtk.plan.Plan;
import org.mmtk.utility.Constants;
import org.mmtk.utility.Log;
import org.mmtk.utility.options.FaultStats;
import org.mmtk.utility.options.ImpulseDelay;
import org.mmtk.utility.options.ImpulseEnabled;
import org.mmtk.utility.options.ImpulseSize;
import org.mmtk.utility.options.KonstantD;
import org.mmtk.utility.options.KonstantI;
import org.mmtk.utility.options.KonstantP;
import org.mmtk.utility.options.KonstantTarget;
import org.mmtk.utility.options.MemoryStats;
import org.mmtk.utility.options.Options;
import org.mmtk.utility.options.PIDEnabled;
import org.mmtk.utility.options.SamplePeriod;
import org.mmtk.utility.options.WindowSize;
import org.mmtk.vm.VM;
import org.vmmagic.pragma.Uninterruptible;
import org.vmmagic.unboxed.Extent;
import org.vmmagic.unboxed.Word;

/**
 * This class is responsible for growing and shrinking the
 * heap size by observing heap utilization and GC load.
 */
@Uninterruptible public abstract class HeapGrowthManager implements Constants {

	/**
	 * The initial heap size (-Xms) in bytes
	 */
	private static Extent initialHeapSize;

	/**
	 * The maximum heap size (-Xms) in bytes
	 */
	private static Extent maxHeapSize;

	/**
	 * The current heap size in bytes
	 */
	private static Extent currentHeapSize;


	private static final double[][] generationalFunction =    
	    {{0.00, 0.00, 0.10, 0.30, 0.60, 0.80, 1.00},
		{ 0.00, 0.90, 0.90, 0.95, 1.00, 1.00, 1.00 },
		{ 0.01, 0.90, 0.90, 0.95, 1.00, 1.00, 1.00 },
		{ 0.02, 0.95, 0.95, 1.00, 1.00, 1.00, 1.00 },
		{ 0.07, 1.00, 1.00, 1.10, 1.15, 1.20, 1.20 },
		{ 0.15, 1.00, 1.00, 1.20, 1.25, 1.35, 1.30 },
		{ 0.40, 1.00, 1.00, 1.25, 1.30, 1.50, 1.50 },
		{ 1.00, 1.00, 1.00, 1.25, 1.30, 1.50, 1.50 } };

	private static final double[][] nongenerationalFunction = 
	   {{0.00, 0.00, 0.10, 0.30, 0.60, 0.80, 1.00},
		{ 0.00, 0.90, 0.90, 0.95, 1.00, 1.00, 1.00 },
		{ 0.02, 0.90, 0.90, 0.95, 1.00, 1.00, 1.00 },
		{ 0.05, 0.95, 0.95, 1.00, 1.00, 1.00, 1.00 },
		{ 0.15, 1.00, 1.00, 1.10, 1.15, 1.20, 1.20 },
		{ 0.30, 1.00, 1.00, 1.20, 1.25, 1.35, 1.30 },
		{ 0.50, 1.00, 1.00, 1.25, 1.30, 1.50, 1.50 },
		{ 1.00, 1.00, 1.00, 1.25, 1.30, 1.50, 1.50 } };

	/**
	 * An encoding of the function used to manage heap size.
	 * The xaxis represents the live ratio at the end of a major collection.
	 * The yaxis represents the GC load (GC time/total time).
	 * The interior of the matrix represents a ratio to shrink or grow
	 * the heap for a given pair of live ratio and GC load.
	 * The constraints on the matrix are:
	 * <ul>
	 * <li> function[0][0] is ignored.
	 * <li> All numbers in the first row must monotonically increase and
	 *      must be in the range from 0 to 1 inclusive.</li>
	 * <li> All numbers in the first column must monotonically increase
	 *      and must be in the range from 0 to 1 inclusive.</li>
	 * <li> There must be 0 and 1 values specified in both dimensions.
	 * <li> For all interior points in the matrix, the value must be
	 *      greater than the liveRatio for that column.</li>
	 * </ul>
	 */
	private static final double[][] function =
			VM.activePlan.constraints().generational() ? 
					generationalFunction : nongenerationalFunction;

	private static final String HGM_STATS_HEADER = 
			"Time,Allocated,Old_Heap_Size,New_Heap_Size,Old_Live_Ratio," +
					"New_Live_Ratio,Short_Term_GC,Long_Term_GC,Resize_Ratio," +
					"Moving_Average,gCPU";

	// Time of last major GC in nanoseconds
	// Total time spent in GC in nanoseconds
	private static long endLastMajorGC;
	private static double accumulatedGCTime;

	// Time of last major GC in CPU microseconds
	// TOtal time spent in GC in CPU microseconds
	private static long endLastMajorGCCPU;
	private static double accumulatedGCTimeCPU;

	// Start time of execution IN MS
	private static long startTime;
	
	// Start time in CPU microseconds
	// private static long startTimeCPU;

	// Total time spent in GC IN MS
	private static long totalGCTime = 0;
	
	// Total time spent in GC in CPU microseconds
	private static long totalGCTimeCPU = 0;

	// is PID enabled?
	private static boolean pidEnabled = false;

	// Memory statistics logging?
	private static boolean memoryStats = false;

	// PID Controller
	public static HeapGrowthPID hgPID;  // @jsinger

	// If we are in 'tuning' mode, are we ready for an impulse?
	public static boolean impulseEnabled = false;
	public static boolean readyForImpulse = false;
	public static boolean impulseFired = false;
	public static int impulseCounter = 0;
	public static int impulseDelay = 2;
	public static float impulseSize;

	// sliding window
	private static final int WINDOW_SIZE = 5;
	private static double slidingWindow[] = new double[WINDOW_SIZE];
	private static boolean slidingWindowInitialised = false;

	// @jsinger - static initialization (at bootimage creation time?)
	// for PID param options
	static {
		Options.konstantP = new KonstantP();
		Options.konstantI = new KonstantI();
		Options.konstantD = new KonstantD();
		Options.konstantTarget = new KonstantTarget();
		Options.windowSize = new WindowSize();
		Options.samplePeriod = new SamplePeriod();
		Options.memoryStats = new MemoryStats();
		Options.faultStats = new FaultStats();
		Options.pidEnabled = new PIDEnabled();
		Options.impulseEnabled = new ImpulseEnabled();
		Options.impulseDelay = new ImpulseDelay();
		Options.impulseSize = new ImpulseSize();
	}

	/**
	 * Initialize heap size parameters and the mechanisms
	 * used to adaptively change heap size.
	 */
	public static void boot(Extent initial, Extent max) {
		initialHeapSize = initial;
		maxHeapSize = max;
		if (initialHeapSize.GT(maxHeapSize))
			maxHeapSize = initialHeapSize;
		currentHeapSize = initialHeapSize;
		VM.events.heapSizeChanged(currentHeapSize);
		if (VM.VERIFY_ASSERTIONS) sanityCheck();
		endLastMajorGC = VM.statistics.nanoTime();
	}

	public static void postBoot() {

		if (Options.memoryStats.getValue()) {
			Log.writeln("HGM:" + HGM_STATS_HEADER);
		}

		memoryStats = Options.memoryStats.getValue();

		pidEnabled = Options.pidEnabled.getValue();
		if (pidEnabled) {
			// do conversion to floating-point numbers here...
			hgPID = new HeapGrowthPID((double)Options.konstantP.getValue()/10000,  // Kp
					(double)Options.konstantI.getValue()/10000, // Ki
					(double)Options.konstantD.getValue()/10000,  // Kd
					(double)Options.konstantTarget.getValue()/10000);  // target value
			Log.writeln("---------------------------------------");
			Log.writeln("Using PID Controller.");
			Log.writeln("PID Parameters are as follows: ");
			Log.write("P Coefficient: ");
			Log.writeln(hgPID.getKp(),4);
			Log.write("I Coefficient: ");
			Log.writeln(hgPID.getKi(),4);
			Log.write("D Coefficient: ");
			Log.writeln(hgPID.getKd(),4);
			Log.write("Target: ");
			Log.writeln(hgPID.getTarget(),4);
			Log.writeln("---------------------------------------");
		}
		HeapGrowthManager.resetStartTime();

		impulseEnabled = Options.impulseEnabled.getValue();
		impulseDelay = Options.impulseDelay.getValue();
		impulseSize = Options.impulseSize.getValue();

	}

	/**
	 * @return the current heap size in bytes
	 */
	public static Extent getCurrentHeapSize() {
		return currentHeapSize;
	}

	/**
	 * Return the max heap size in bytes (as set by -Xmx).
	 *
	 * @return The max heap size in bytes (as set by -Xmx).
	 */
	public static Extent getMaxHeapSize() {
		return maxHeapSize;
	}

	/**
	 * Return the initial heap size in bytes (as set by -Xms).
	 *
	 * @return The initial heap size in bytes (as set by -Xms).
	 */
	public static Extent getInitialHeapSize() {
		return initialHeapSize;
	}

	/**
	 * Forcibly grow the heap by the given number of bytes.
	 * Used to provide headroom when handling an OutOfMemory
	 * situation.
	 * @param size number of bytes to grow the heap
	 */
	public static void overrideGrowHeapSize(Extent size) {
		currentHeapSize = currentHeapSize.plus(size);
		VM.events.heapSizeChanged(currentHeapSize);
	}

	/**
	 * Record the time taken by the current GC;
	 * used to compute gc load, one of the inputs
	 * into the heap size management function
	 * Kept in milliseconds
	 */
	public static void recordGCTime(double time) {
		accumulatedGCTime += time;
		totalGCTime += time;
	}
	
	/**
	 * Record the time taken by the current GC;
	 * used to compute gc load
	 * Recorded in microseconds, CPU time
	 */
	public static void recordGCTimeCPU(long time) {
		accumulatedGCTimeCPU += time;
		totalGCTimeCPU += time;
	}

	/**
	 * Reset timers used to compute gc load
	 */
	public static void reset() {
		endLastMajorGC = VM.statistics.nanoTime();
		endLastMajorGCCPU = getCPUTime();
		accumulatedGCTime = 0;
		accumulatedGCTimeCPU = 0;
	}

	/**
	 * Decide how to grow/shrink the heap to respond
	 * to application's memory usage.
	 * @return true if heap size was changed, false otherwise
	 */
	public static boolean considerHeapSize() {
		
		Extent oldSize = currentHeapSize;
		Extent reserved = Plan.reservedMemory();
		double liveRatio = reserved.toLong() / ((double) currentHeapSize.toLong());
		double gcLoad = HeapGrowthManager.getGCLoad();
		double gcLoadCPU = HeapGrowthManager.getGCLoadCPU();
		updateSlidingWindow(gcLoadCPU);

		// Calculate ratio via the 'old school' hack, or else by the PID controller
		double ratio;
		
		if (pidEnabled && (hgPID != null)) {
			runPID(VM.getTotalMemAllocated());
			ratio = 1.0 + hgPID.getInput();
			// Don't shrink the heap too much if limited by live ratio.
			if (ratio < liveRatio) {
				ratio = liveRatio + 0.01;
			}
		} else if (pidEnabled) {
			ratio = 1.0; // don't do anything until PID ready, if enabled
		} else if (impulseEnabled) {
			if (readyForImpulse) {
				ratio = considerImpulse();
			} else {
				ratio = 1.0;
			}
		// Otherwise use default controller
		} else {
			ratio = computeHeapChangeRatio(liveRatio,gcLoad);
		} 

		// calculate new heap size
		Extent newSize = Word.fromIntSignExtend((int)(ratio * (double) 
				(oldSize.toLong()>>LOG_BYTES_IN_MBYTE)))
				.lsh(LOG_BYTES_IN_MBYTE).toExtent(); 
				// do arith in MB to avoid overflow

		if (memoryStats) {
			// @drw
			Log.write("HGM:");
			Log.write(VM.statistics.nanoTime());
			Log.write(",");
			Log.write(VM.getTotalMemAllocated());
			Log.write(",");
			Log.write(oldSize.toInt());
			Log.write(",");
			Log.write(newSize.toInt());
			Log.write(",");
			Log.write(liveRatio,4);
			Log.write(",");
			Log.write(getLiveRatio(),4);
			Log.write(",");
			Log.write(gcLoad,4);
			Log.write(",");
			Log.write(getTotalGCOverhead(),4);
			Log.write(",");
			Log.write(ratio,4);
			Log.write(",");
			Log.write(getSlidingWindowValue(),4);
			Log.write(",");
			Log.writeln(gcLoadCPU,4);
			Log.flush();
		}


		if (newSize.LT(reserved)) newSize = reserved;
		newSize = newSize.plus(BYTES_IN_MBYTE - 1).toWord().
			rshl(LOG_BYTES_IN_MBYTE).lsh(LOG_BYTES_IN_MBYTE)
		 	.toExtent(); // round to next megabyte
		
		if (newSize.GT(maxHeapSize)) newSize = maxHeapSize;
		
		if (newSize.NE(oldSize) && newSize.GT (Extent.zero())) {
			// Heap size is going to change
			currentHeapSize = newSize;   

			if (Options.verbose.getValue() >= 2) {
				Log.write("GC Message: Heap changed from "); Log.writeDec(oldSize.toWord().rshl(LOG_BYTES_IN_KBYTE));
				Log.write("KB to "); Log.writeDec(newSize.toWord().rshl(LOG_BYTES_IN_KBYTE));
				Log.writeln("KB");
			}
			
			VM.events.heapSizeChanged(currentHeapSize);
			
			return true;
			
		} else {
			
			return false;
			
		}
	}

	private static double computeHeapChangeRatio(double liveRatio, 
												 double gcLoad) {
	

		if (liveRatio > 1) {
			// Perhaps indicates bad bookkeeping in MMTk?
			Log.write("GCWarning: Live ratio greater than 1: ");
			Log.writeln(liveRatio);
			liveRatio = 1;
		}
		
		if (gcLoad > 1) {
			if (gcLoad > 1.0001) {
				Log.write("GC Error: GC load was greater than 1!! ");
				Log.writeln(gcLoad);
				Log.write("GC Error:\ttotal time (ms) "); 
//				Log.writeln(totalTime);
				Log.write("GC Error:\tgc time (ms) "); 
				Log.writeln(accumulatedGCTime);
			}
			gcLoad = 1;
		}
		if (VM.VERIFY_ASSERTIONS) VM.assertions._assert(liveRatio >= 0);
		if (VM.VERIFY_ASSERTIONS && gcLoad < -0.0) {
			Log.write("gcLoad computed to be "); 
			Log.writeln(gcLoad);
			Log.write("\taccumulateGCTime was (ms) "); 
			Log.writeln(accumulatedGCTime);
			Log.write("\ttotalTime was (ms) "); 
//			Log.writeln(totalTime);
			if (VM.VERIFY_ASSERTIONS) VM.assertions._assert(false);
		}

		if (Options.verbose.getValue() > 2) {
			Log.write("Live ratio "); Log.writeln(liveRatio);
			Log.write("GCLoad     "); Log.writeln(gcLoad);
		}

		// (2) Find the 4 points surrounding gcLoad and liveRatio
		int liveRatioUnder = 1;
		int liveRatioAbove = function[0].length - 1;
		int gcLoadUnder = 1;
		int gcLoadAbove = function.length - 1;
		while (true) {
			if (function[0][liveRatioUnder+1] >= liveRatio) break;
			liveRatioUnder++;
		}
		while (true) {
			if (function[0][liveRatioAbove-1] <= liveRatio) break;
			liveRatioAbove--;
		}
		while (true) {
			if (function[gcLoadUnder+1][0] >= gcLoad) break;
			gcLoadUnder++;
		}
		while (true) {
			if (function[gcLoadAbove-1][0] <= gcLoad) break;
			gcLoadAbove--;
		}

		// (3) Compute the heap change ratio
		double factor = function[gcLoadUnder][liveRatioUnder];
		double liveRatioFraction =
				(liveRatio - function[0][liveRatioUnder]) /
				(function[0][liveRatioAbove] - function[0][liveRatioUnder]);
		double liveRatioDelta =
				function[gcLoadUnder][liveRatioAbove] - 
				function[gcLoadUnder][liveRatioUnder];
		factor += (liveRatioFraction * liveRatioDelta);
		double gcLoadFraction =
				(gcLoad - function[gcLoadUnder][0]) /
				(function[gcLoadAbove][0] - function[gcLoadUnder][0]);
		double gcLoadDelta =
				function[gcLoadAbove][liveRatioUnder] - 
				function[gcLoadUnder][liveRatioUnder];
		factor += (gcLoadFraction * gcLoadDelta);

		if (Options.verbose.getValue() > 2) {
			Log.write("Heap adjustment factor is ");
			Log.writeln(factor);
		}
		return factor;
	}

	/**
	 * Check that function satisfies the invariants
	 */
	private static void sanityCheck() {
		// Check live ratio
		double[] liveRatio = function[0];
		if (VM.VERIFY_ASSERTIONS) VM.assertions._assert(liveRatio[1] == 0);
		if (VM.VERIFY_ASSERTIONS) VM.assertions.
			_assert(liveRatio[liveRatio.length-1] == 1);
		for (int i = 2; i < liveRatio.length; i++) {
			if (VM.VERIFY_ASSERTIONS) VM.assertions
				._assert(liveRatio[i-1] < liveRatio[i]);
			for (int j = 1; j < function.length; j++) {
				if (VM.VERIFY_ASSERTIONS) VM.assertions
					._assert(function[j][i] >= 1 || function[j][i] > liveRatio[i]);
			}
		}

		// Check GC load
		if (VM.VERIFY_ASSERTIONS) VM.assertions.
			_assert(function[1][0] == 0);
		int len = function.length;
		if (VM.VERIFY_ASSERTIONS) VM.assertions.
			_assert(function[len-1][0] == 1);
		for (int i = 2; i < len; i++) {
			if (VM.VERIFY_ASSERTIONS) VM.assertions
				._assert(function[i-1][0] < function[i][0]);
		}

		// Check that we have a rectangular matrix
		for (int i = 1; i < function.length; i++) {
			if (VM.VERIFY_ASSERTIONS) VM.assertions
				._assert(function[i-1].length == function[i].length);
		}
	}

	// Return GC load (for logging only)
	public static double getGCLoad() {
		long totalNanos = VM.statistics.nanoTime() - endLastMajorGC;
		double totalTime = VM.statistics.nanosToMillis(totalNanos);
		return accumulatedGCTime / totalTime;
	}
	
	public static double getGCLoadCPU() {
		long totalTimeCPU = getCPUTime() - endLastMajorGCCPU;
		return accumulatedGCTimeCPU / totalTimeCPU;
	}

	public static long getCPUTime() {
		// drw
		// inserted to test CPU usage code
		long[] cpuTimes = VM.getCPUTime();
		long total = 0;
		// Self, system, seconds
		total += cpuTimes[0] * 1000000;
		// Self, system, microseconds
		total += cpuTimes[1];
		// Self, user, seconds
		total += cpuTimes[2] * 1000000;
		// Self, user, microseconds
		total += cpuTimes[3];
		// Children, system, seconds
		total += cpuTimes[4] * 1000000;
		// Children, system, microseconds
		total += cpuTimes[5];
		// Children, user, seconds
		total += cpuTimes[6] * 1000000;
		// Children, user, microseconds
		total += cpuTimes[7];
		
		/*
		 	Log.writeln("HGM: Self System Seconds:\t" + cpuTimes[0]);
		 	Log.writeln("HGM: Self System Microseconds:\t" + cpuTimes[1]);
			Log.writeln("HGM: Self User Seconds:\t" + cpuTimes[2]);
			Log.writeln("HGM: Self User Microseconds:\t" + cpuTimes[3]);
			Log.writeln("HGM: Children System Seconds:\t" + cpuTimes[4]);
			Log.writeln("HGM: Children System Microseconds:\t" + cpuTimes[5]);
			Log.writeln("HGM: Children User Seconds:\t" + cpuTimes[6]);
			Log.writeln("HGM: Children User Microseconds:\t" + cpuTimes[7]);
			Log.flush();
		*/
		return total;
	}
	
	// @jsinger - for PID control - 
	// an alternative output variable is
	// live ratio
	public static double getLiveRatio() {
		Extent reserved = Plan.reservedMemory();
		double liveRatio = reserved.toLong() / 
			((double) currentHeapSize.toLong());
		return liveRatio;
	}

	public static double getTotalGCOverhead() {
		return (double) totalGCTime / (double) 
			(VM.statistics.nanosToMillis(VM.statistics.nanoTime()) - startTime);
	}

	// All times in ms
	public static void resetStartTime() {
		startTime = (long)VM.statistics.nanosToMillis(VM.statistics.nanoTime());
		//startTimeCPU = getCPUTime();
	}

	// Update PID
	// uses a running-average sliding window
	public static void runPID(long bytes) {
		
		double total = 0;
		for (int i=0;i<slidingWindow.length;i++) {
			total += slidingWindow[i];
		}
		
		hgPID.runOneIter(bytes,total / slidingWindow.length);
		
	}
	
	public static double getSlidingWindowValue() {
		
		double total = 0;
		for (int i=0;i<slidingWindow.length;i++) {
			total += slidingWindow[i];
		}
		return total / slidingWindow.length;

		
	}
	
	public static void updateSlidingWindow(double gcLoadCPU) {
		
		// could use a circular buffer for efficiency
		if (!slidingWindowInitialised) {
			double t;
			if (!pidEnabled) {
				t = getGCLoad(); // sensible default
			} else {
				t = hgPID.getTarget();
			}
			for (int i=0;i<slidingWindow.length;i++) {
				slidingWindow[i] = t;
			}
			slidingWindowInitialised = true;
		}

		for (int i=0;i<slidingWindow.length-1;i++) {
			slidingWindow[i] = slidingWindow[i+1];
		}
		slidingWindow[slidingWindow.length-1] = gcLoadCPU;
				
	}

	public static void readyForImpulse() {
		readyForImpulse = true;  
		Log.writeln("IMP: Ready for impulse");
	}

	private static float considerImpulse() {

		float ratio = 1.0f;

		if (!impulseFired) {

			impulseCounter++;

			if (impulseCounter == impulseDelay) {
				ratio = impulseSize;
				impulseFired = true;
				Log.writeln("IMP:Impulse fired: " + ratio);
			}

		}

		return ratio;

	}

}
